package com.company.algo.tree;

import com.company.algo.pojo.TreeNode;

/**
 * 力扣第 106 题
 * 通过后序和中序遍历结果构造二叉树
 */
public class BuildTree2 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;
        return buildTree(inorder,0,len-1, postorder,0,len-1);
    }

    TreeNode buildTree(int[] inorder, int inStart, int inEnd,
                       int[] postorder, int postStart, int postEnd) {
        if (postStart > postEnd) return null;
        int rootVal = postorder[postEnd];
        int rootIdx = 0;
        for (int i = inStart; i <= inEnd ; i++) {
            if (rootVal == inorder[i]){
                rootIdx = i;
                break;
            }
        }
        int rightLen = inEnd - rootIdx;
        TreeNode root = new TreeNode(rootVal);
        root.right = buildTree(inorder,rootIdx+1,inEnd,
                    postorder,postEnd-rightLen,postEnd-1);
        root.left = buildTree(inorder,inStart,rootIdx-1,
                    postorder,postStart,postEnd-rightLen-1);
        return root;
    }

    public static void main(String[] args) {
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        BuildTree2 Main = new BuildTree2();
        System.out.println(Main.buildTree(inorder,postorder));
    }
}
